<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title> - 友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="多路查找树——B树与B&#43;树 B/B&#43; 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
 B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）   有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。
  B&#43;树：B&#43;树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。  B&#43;树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B&#43;树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B&#43;树应运而生。B&#43;树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
 B/B&#43;树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n） B/B&#43;树空间复杂度：O(n)，因为有指针（B树还有关键字）  1. B树 2-3树是一种特殊的B树。
M阶B树的定义：
 每一个节点最多有 m 个子节点 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点 如果根节点不是叶子节点，那么它至少有两个子节点 有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字） 所有的叶子节点都在同一层   m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。
 2. B树的查找 3. B树的插入 4. B&#43;树 M阶B&#43;树是M阶B树的变种树：
 B&#43; 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据） 通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联） 一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。  不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。" />

  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/15%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BEb%E6%A0%91%E4%B8%8Eb&#43;%E6%A0%91/" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="" />
<meta property="og:description" content="多路查找树——B树与B&#43;树 B/B&#43; 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
 B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）   有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。
  B&#43;树：B&#43;树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。  B&#43;树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B&#43;树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B&#43;树应运而生。B&#43;树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
 B/B&#43;树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n） B/B&#43;树空间复杂度：O(n)，因为有指针（B树还有关键字）  1. B树 2-3树是一种特殊的B树。
M阶B树的定义：
 每一个节点最多有 m 个子节点 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点 如果根节点不是叶子节点，那么它至少有两个子节点 有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字） 所有的叶子节点都在同一层   m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。
 2. B树的查找 3. B树的插入 4. B&#43;树 M阶B&#43;树是M阶B树的变种树：
 B&#43; 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据） 通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联） 一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。  不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/15%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BEb%E6%A0%91%E4%B8%8Eb&#43;%E6%A0%91/" />

<meta itemprop="name" content="">
<meta itemprop="description" content="多路查找树——B树与B&#43;树 B/B&#43; 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
 B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）   有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。
  B&#43;树：B&#43;树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。  B&#43;树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B&#43;树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B&#43;树应运而生。B&#43;树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
 B/B&#43;树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n） B/B&#43;树空间复杂度：O(n)，因为有指针（B树还有关键字）  1. B树 2-3树是一种特殊的B树。
M阶B树的定义：
 每一个节点最多有 m 个子节点 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点 如果根节点不是叶子节点，那么它至少有两个子节点 有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字） 所有的叶子节点都在同一层   m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。
 2. B树的查找 3. B树的插入 4. B&#43;树 M阶B&#43;树是M阶B树的变种树：
 B&#43; 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据） 通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联） 一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。  不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。">



<meta itemprop="wordCount" content="136">



<meta itemprop="keywords" content="" />
<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content=""/>
<meta name="twitter:description" content="多路查找树——B树与B&#43;树 B/B&#43; 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
 B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）   有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。
  B&#43;树：B&#43;树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。  B&#43;树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B&#43;树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B&#43;树应运而生。B&#43;树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。
 B/B&#43;树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n） B/B&#43;树空间复杂度：O(n)，因为有指针（B树还有关键字）  1. B树 2-3树是一种特殊的B树。
M阶B树的定义：
 每一个节点最多有 m 个子节点 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点 如果根节点不是叶子节点，那么它至少有两个子节点 有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字） 所有的叶子节点都在同一层   m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。
 2. B树的查找 3. B树的插入 4. B&#43;树 M阶B&#43;树是M阶B树的变种树：
 B&#43; 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据） 通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联） 一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。  不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          <article class="post bg-white">
    
    <header class="post-header">
      <h1 class="post-title"></h1>
      
      <div class="post-meta">
        <time datetime="0001-01-01" class="post-time">
          0001-01-01
        </time>
        
        <span class="more-meta"> 约 136 字 </span>
          <span class="more-meta"> 预计阅读 1 分钟 </span>

        
        

        
        
      </div>
    </header>

    
    
<div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">文章目录</h2>
  <div class="post-toc-content">
    <nav id="TableOfContents">
<ul>
<li><a href="#多路查找树-b树与b-树">多路查找树——B树与B+树</a>
<ul>
<li><a href="#1-b树">1. B树</a></li>
<li><a href="#2-b树的查找">2. B树的查找</a></li>
<li><a href="#3-b树的插入">3. B树的插入</a></li>
<li><a href="#4-b-树">4. B+树</a></li>
<li><a href="#5-b-树插入关键字">5. B+树插入关键字</a></li>
<li><a href="#6-b-树删除关键字">6. B+树删除关键字</a></li>
<li><a href="#7-b-树与索引">7. B+树与索引</a></li>
</ul></li>
</ul>
</nav>
  </div>
</div>

    
    <div class="post-content">
      

<h1 id="多路查找树-b树与b-树">多路查找树——B树与B+树</h1>

<p>B/B+ 树就是N叉（N-ary）平衡树了，每个结点可以有更多的孩子，新的值可以插在已有的结点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。</p>

<ul>
<li>B树：B-tree（B-tree树即B树，B即Balanced，平衡的意思）</li>
</ul>

<blockquote>
<p>有的文章里面出现的B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。</p>
</blockquote>

<ul>
<li>B+树：B+树是B树的变种树，有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子结点。</li>
</ul>

<p>B+树用在磁盘文件组织、数据索引和数据库索引。数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。</p>

<ul>
<li>B/B+树时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n）</li>
<li>B/B+树空间复杂度：O(n)，因为有指针（B树还有关键字）</li>
</ul>

<h2 id="1-b树">1. B树</h2>

<p>2-3树是一种特殊的B树。</p>

<p><img src="http://sweeat.me/2-3树.png" alt="2-3树" /></p>

<p>M阶B树的定义：</p>

<p><img src="http://sweeat.me/B树.png" alt="B树" /></p>

<ul>
<li>每一个节点最多有 m 个子节点</li>
<li>每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点</li>
<li>如果根节点不是叶子节点，那么它至少有两个子节点</li>
<li>有 k 个子节点的非叶子节点拥有 k − 1 个关键字（即非叶子结点有k个指针和k-1个关键字）</li>
<li>所有的叶子节点都在同一层</li>
</ul>

<blockquote>
<p>m/2的限制一是为了保证存储密度，二是避免树结构退化，保证其在磁盘存储器中的存储优势。正因为 b 树是一个稳定的多叉结构，每一个节点有多个 key 和分支。在磁盘存储器这样的 查找速度慢(硬件条件限制)，以存储块(一个相对较大的块)为单位读取的 硬件结构中，才有了明显的优势。</p>
</blockquote>

<h2 id="2-b树的查找">2. B树的查找</h2>

<p><img src="http://sweeat.me/B树查找.png" alt="B树查找" /></p>

<p><img src="http://sweeat.me/B树查找性能.png" alt="B树查找性能" /></p>

<h2 id="3-b树的插入">3. B树的插入</h2>

<p><img src="http://sweeat.me/B树插入1.png" alt="B树插入1" />
<img src="http://sweeat.me/B树插入2.png" alt="B树插入2" />
<img src="http://sweeat.me/B树插入3.png" alt="B树插入3" />
<img src="http://sweeat.me/B树插入4.png" alt="B树插入4" /></p>

<h2 id="4-b-树">4. B+树</h2>

<p>M阶B+树是M阶B树的变种树：</p>

<p><img src="http://sweeat.me/B+树.jpg" alt="B+树" /></p>

<ul>
<li>B+ 树中的非叶子结点不存储关键字数据，只是存储索引；（B 树中的结点存储数据）</li>
<li>通过链表将叶子结点串联在一起，这样可以方便按区间查找；（B树叶子结点没有串联）</li>
<li>一般情况，根结点会被存储在内存中，其他结点存储在磁盘中。</li>
</ul>

<p>不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。</p>

<h2 id="5-b-树插入关键字">5. B+树插入关键字</h2>

<p>在B+树中插入关键字时，需要注意以下几点：</p>

<ul>
<li>插入的操作全部都在叶子结点上进行，且不能破坏关键字自小而大的顺序；</li>
<li>由于 B+树中各结点中存储的关键字的个数有明确的范围，做插入操作可能会出现结点中关键字个数超过阶数的情况，此时需要将该结点进行“分裂”；</li>
</ul>

<p>M阶B+树中做插入关键字的操作，有以下 3 种情况：</p>

<ol>
<li>若被插入关键字所在的结点，其含有关键字数目小于阶数 M，则直接插入结束</li>
<li>若被插入关键字所在的结点，其含有关键字数目等于阶数 M，则需要将该结点分裂为两个结点，一个结点包含⌊M/2⌋，另一个结点包含⌈M/2⌉。同时，将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M，则插入操作完成。</li>
<li>在第 2 情况中，如果上移操作导致其双亲结点中关键字个数大于 M，则应继续分裂其双亲结点。</li>
</ol>

<p>注意：如果插入的关键字比当前结点中的最大值还大，破坏了B+树中从根结点到当前结点的所有索引值，此时需要及时修正后，再做其他操作。例如，在图 1 的 B+树种插入关键字 100，由于其值比 97 还大，插入之后，从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。</p>

<h2 id="6-b-树删除关键字">6. B+树删除关键字</h2>

<p>在 B+树中做删除关键字的操作，采取如下的步骤：</p>

<ul>
<li>删除该关键字，如果不破坏 B+树本身的性质，直接完成操作；</li>
<li>如果删除操作导致其该结点中最大（或最小）值改变，则应相应改动其父结点中的索引值；</li>
<li>在删除关键字后，如果导致其结点中关键字个数不足，有两种方法：一种是向兄弟结点去借，另外一种是同兄弟结点合并。（注意这两种方式有时需要更改其父结点中的索引值。）</li>
</ul>

<h2 id="7-b-树与索引">7. B+树与索引</h2>

<p>数据库索引需求：</p>

<ul>
<li>根据某个值查找数据，比如 select * from user where id=1234；</li>
<li>根据区间值来查找某些数据，比如 select * from user where id &gt; 1234 and id &lt; 2345。</li>
</ul>

<ol>
<li>为什么不使用散列表呢？</li>
</ol>

<p>虽然散列表时间复杂度是O(1)，但是不支持按照区间快速查找数据。</p>

<ol>
<li>为什么不使用平衡二叉树呢？</li>
</ol>

<p>尽管平衡二叉查找树查询的性能也很高，时间复杂度是 O(logn)。而且，对树进行中序遍历，我们还可以得到一个从小到大有序的数据序列，但这仍然不足以支持按照区间快速查找数据。并且，对于大数据量持久化存储，二叉排序树的深度k会很大，每次查询需要进行多次磁盘IO。</p>

<p>二叉查找树，经过改造之后，支持区间查找的功能就实现了。为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的结点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子结点串在一条链表上，链表中的数据是从小到大有序的。</p>

<p>不管是内存中的数据，还是磁盘中的数据，操作系统都是按页（一页大小通常是 4KB，这个值可以通过 getconfig PAGE_SIZE 命令查看）来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次 IO 操作。所以，我们在选择 m 大小的时候，要尽量让每个结点的大小等于一个页的大小。读取一个结点，只需要一次磁盘 IO 操作。</p>

<p>数据的写入过程，会涉及索引的更新，这是索引导致写入变慢的主要原因。</p>

    </div>

    
    
<div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">文章作者</span>
    <span class="item-content">yixy</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">上次更新</span>
    <span class="item-content">
      0001-01-01
      
    </span>
  </p>
  
  <p class="copyright-item">
    <span class="item-title">许可协议</span>
    <span class="item-content"><a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank">CC BY-NC-ND 4.0</a></span>
  </p>
</div>


    
    
<div class="post-reward">
  <input type="checkbox" name="reward" id="reward" hidden />
  <label class="reward-button" for="reward">赞赏支持</label>
  <div class="qr-code">
    
    
      <label class="qr-code-image" for="reward">
        <img class="image" src="/youzhilane/img/about/wechat.jpg">
        <span>微信打赏</span>
      </label>
    
  </div>
</div>

    <footer class="post-footer">
      

      
      <nav class="post-nav">
        
          <a class="prev" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/14%E6%A0%91%E8%A1%A8%E6%9F%A5%E6%89%BE%E7%BA%A2%E9%BB%91%E6%A0%91/">
            
            <i class="iconfont">
              <svg  class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M691.908486 949.511495l75.369571-89.491197c10.963703-12.998035 10.285251-32.864502-1.499144-44.378743L479.499795 515.267417 757.434875 204.940602c11.338233-12.190647 11.035334-32.285311-0.638543-44.850487l-80.46666-86.564541c-11.680017-12.583596-30.356378-12.893658-41.662889-0.716314L257.233596 494.235404c-11.332093 12.183484-11.041474 32.266891 0.657986 44.844348l80.46666 86.564541c1.772366 1.910513 3.706415 3.533476 5.750981 4.877077l306.620399 321.703933C662.505829 963.726242 680.945807 962.528973 691.908486 949.511495z"></path>
</svg>

            </i>
            <span class="prev-text nav-default"></span>
            <span class="prev-text nav-mobile">上一篇</span>
          </a>
        
          <a class="next" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/16%E6%95%A3%E5%88%97%E8%A1%A8%E6%9F%A5%E6%89%BE/">
            <span class="next-text nav-default"></span>
            <span class="prev-text nav-mobile">下一篇</span>
            
            <i class="iconfont">
              <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M332.091514 74.487481l-75.369571 89.491197c-10.963703 12.998035-10.285251 32.864502 1.499144 44.378743l286.278095 300.375162L266.565125 819.058374c-11.338233 12.190647-11.035334 32.285311 0.638543 44.850487l80.46666 86.564541c11.680017 12.583596 30.356378 12.893658 41.662889 0.716314l377.434212-421.426145c11.332093-12.183484 11.041474-32.266891-0.657986-44.844348l-80.46666-86.564541c-1.772366-1.910513-3.706415-3.533476-5.750981-4.877077L373.270379 71.774697C361.493148 60.273758 343.054193 61.470003 332.091514 74.487481z"></path>
</svg>

            </i>
          </a>
      </nav>
    </footer>
  </article>

  
  
  
  

  
  

  

  
  

  

  

  

    

  

        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
